Video ca nhạc "Gentleman" được đăng lên YouTube vào thứ bảy ngày 13/4/ 2013. Nội dung video ca nhạc nhằm phê phán những kẻ "tốt nước sơn hơn tốt gỗ". PSY đóng vai một người đàn ông tuy ăn mặc bảnh bao, xài đồ hiệu đắt tiền nhưng anh ta luôn cư xử khiếm nhã, vô học với mọi người như: phá hoại của công, bắt người khác ngửi mùi đánh rắm của mình, hất phụ nữ té bằng nhiều cách, ngăn không cho người đang đau bụng đi vệ sinh, lột bikini phụ nữ, làm trò điên trên phố, phá trận bóng của trẻ em,...

Một điệu nhảy gắn liền với bài hát giới thiệu trong video được bắt nguồn từ điệu nhảy trong bài hát "Abracadabra" của nhóm nhạc Hàn Quốc Brown Eyed Girls. Thành viên Ga-In của nhóm nhạc này cũng tham gia video ca nhạc này.[17] PSY cho biết đã trả tiền tác quyền cho biên đạo của 'Brown Eyed Girls'.[18]

Phát hành

Video ca nhạc "Gentleman" được đăng lên YouTube vào thứ bảy ngày 13/4/ 2013. Bài hát được phát hành vào nửa đêm ngày 12 tháng 4 trên từng múi giờ.[19] Nhiều người tìm cách truy cập bài hát qua mạng từ sớm bị chặn bởi công ty thu âm của PSY,[7] tuy nhiên tạp chí Time báo cáo là vẫn có đối tượng tiếp cận được với bài hát trước giờ.[6] PSY khi được hỏi vì sao phát hành bài hát sớm một ngày so với buổi hòa nhạc "Happening", anh trả lời qua Twitter rằng "cause We Gotta Sing Along" (chúng tôi sẽ hát cùng nhau).[20]

Ngày 18/4, video Gentleman bị Đài truyền hình nhà nước của Hàn Quốc, hệ thống phát thanh truyền hình Hàn Quốc (KBS) cấm chiếu do có cảnh PSY "phá hoại tài sản công cộng" khi anh "sút" một nón giao thông đề chữ "cấm đậu xe".[21]